[Codeforces 1384 D]GameGame 题解

闲话:这场做出ACD可以到前百名.

原题链接:Codeforces 1384 D
题目大意:有两个人初始分数都是$0$,一共有$n$个值$a_i$.每一步操作可以让自己的分数和其中任意一个$a_i$异或起来,并删掉这个$a_i$.最后两边谁的值更大谁获胜.问先手是否必胜,或是平局.
数据范围:
$1 \leq n \leq 10^5$
$0 \leq a_i \leq 10^9$

先把特殊情况抠掉:平局的时候两边的分数是相等的,因为两边的分数就是取两个不同的集合,整个集合的并集是原来的序列$a$,交集是空集,所以两边的分数异或起来是$0$说明整个序列的异或和为$0$.因此整个序列异或和$x=0$的时候,游戏为平局.
如果$x$不为$0$.因为整个$x$应该是两个数的异或和,即两边的分数的异或和,那么$x$的某一位如果是$1$的话代表着有一边是$1$而有一边是$0$,也就是说,两边的分数在这一位上出现了不同,这一位就是决定了两边的分数谁更大的关键位置.假设这一位是$i$,满足x >> i & 1这个表达式为真.显然两边的分数在这一位上是各取了原先$a$序列里所有的数这一位上的数位值,再异或起来得到的(因为异或是不进位的,本位的值与其他位的元素无关),所以这一位上到底是先手分的$1$还是后手的分到$1$应该要看整个序列里的所有元素这一位上具体是多少.显然只有两种取值$0$或$1$,分别记为$c0$和$c1$.
多种情况,一个一个来分析:
①如果$c1$是偶数.
由于本位置上异或和应该是$1$,所以与之矛盾了,因为偶数个$1$必然组成$0$,而之后再有多少个$0$都不会让结果变得更大,因此这个情况其实是矛盾的.
②如果$c1$是奇数
在这个情况下,$1$的数量其实是有很大影响的,通过枚举可以发现,如果是奇数个$1$的话,实际上是有两种情况的:因为在有$4$的倍数个$1$和单个的$1$的时候,组合起来的异或值还是$1$,但是如果去掉$4$的倍数的部分之后,余的是$3$个$1$,这个时候就会造成一个$0 \oplus 0 \oplus 1$的情况,他们的异或和是$0$.这里要继续划分情况讨论.

1'如果$c1 \% 4 = 1$即余下$1$只有一个的情况.
在这种情形下,对于我这个先手的人来说,我只需要先拿掉一个$1$,那么接下来我要得到一个异或和是$0$的方案,接下来对手怎么做我就怎么做,这样的话,我手上是必然得到奇数个$1$和若干个个$0$的,这样结束之后,我手上偶数个$1$得到的就是$0$,最后多一个$1$,我就胜利了.
也就是说在1'这个情形下,先手是必胜的,因为他可以抢掉奇数的那一个$1$.

2'如果$c1 \%4 = 3$即余下$1$是有三个的情况.
这种情况可能就难看了一些,因为他是余下了三个.作为先手,还是按之前的策略来抢出一个奇数的$1$,但是此时后手完全可以仿照先手的镜像操作,来使先手得到偶数个的$1$.不过这一点不是总能实现的:假设当$c0$的个数是偶数的时候,由于是偶数,所以整个操作序列里可以把偶数的$0$的部分全部删去,只看留下的$1$的操作:既然是余数是$3$,那么整个局面除了$4$的倍数的部分,一定是一个$111$的序列,即先手必然取到偶数个$1$导致手上是$0$.也就是说如果$c0 \%2 == 0$,此时就是必胜的.不过另外一种情况,也就是当$c0$的个数也是奇数的时候,会补齐操作序列里的数量,就是说此时局面又可以等价成$1110$这个情况,那么我先手选择掉$0$的话,就可以做到必胜.此时对于先手来说又是一个必胜的.

综上,整个局面当且仅当$c1 \%4 = 3$且$c0 \% 2 == 0$时后手必胜,其余情况先手必胜.

以上都是我的个人的思考过程,想通了之后,这个问题可以用抵消的考虑方式快速的得到结论,下面说明一下:
首先,偶数个$1$或者偶数个$0$必然得到$0$,对结果是没有影响的,所以局面可以等价的把他们删掉.因此第一种情况是完全不需要考虑的.
其次第二种情况里,也就是说$c1$是奇数的时候的时候,又有两种情况了:因为对于奇数情况来说,如果模$4$余$1$,得到的是$1$,如果得到的是$3$,则是$0$.为什么会有这个问题?可以按消去的想法简单的想一下,就是说偶数的部分虽然是可以消掉的,但是不一定是完全能消的,比如在$c1 \%4 == 3$的前提下,如果$0$是偶数个,则偶数个$0$很显然是可以消掉而毫无影响,但是$1$不行,因为偶数个$0$消掉之后,先手的人在这里必然会拿到两个$1$,而不能直接按消去的办法直接把他变成$1$.从另外一个角度来说明,$c1$是奇数,但是也要看他去掉$1$之后有几个一对$1$,这里面有几对额外的一对$1$,决定了他最后是$1$还是$0$.这一点需要特别注意.在这之后第二种情况下就分别对应$111$和$1110$两种情况了,情形简化之后就很好考虑了.剩下的实现也比较简单,就不多提了.

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int T;cin >> T;
	while(T--)
	{
		int n;cin >> n;
		int xs = 0;
		vector<int> a(n);
		for (auto &i : a)
		{
			cin >> i;
			xs ^= i;
		}
		if(!xs)	cout << "DRAW\n";
		else
		{
			for(int i = 31;i >= 0;--i)
			{
				int ch = xs >> i & 1;
				if(!ch)	continue;
				int c1 = 0,c0 = 0;
				for(auto& v : a)
				{
					if(v >> i & 1)	++c1;
					else ++c0;
				}
				if(c1 % 4 == 3 && c0 % 2 == 0)	cout << "LOSE\n";
				else cout << "WIN\n";
				break;
			}
		}
	}
    return 0;
}